package com.leetcode;

import java.util.TreeSet;

/**
 * 220. 存在重复元素 III (困难)
 * <p>
 * 给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，
 * 同时又满足 abs(i - j) <= k 。
 * 如果存在则返回 true，不存在返回 false。
 */
public class LeetCode220 {

    public static void main(String[] arg0) {
        int[] nums = new int[]{1, 2, 3, 1};
        int k = 3;
        int t = 0;
        System.out.println("是否存在重复元素 = " + containsNearbyAlmostDuplicate(nums, k, t));
    }

    public static boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        int length = nums.length;
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < length; i++) {
            // 用于返回等于或大于给定元素(ele)的最低元素(如果存在)，否则返回null。
            Long ceiling = set.ceiling((long) nums[i] - (long) valueDiff);
            if (ceiling != null && ceiling <= ((long) nums[i] + (long) valueDiff)) {
                return true; // 下面的元素移除不考虑移除的不是第一个，因为如果有相同元素，这里就返回true了
            }
            set.add((long) nums[i]);
            // set充当滑动窗口，数量超过 indexDiff 就移除第一个
            // 最多比较 indexDiff+1 个元素，前面已经对set中所有元素和nums[i]做了比较，所以set的size要维持在 indexDiff 个
            // 题解中的判断是 (i >= indexDiff) ，也就是从 i==indexDiff 的时候就开始移除第一个，set的size也是维持在 indexDiff 个
            if (set.size() > indexDiff) {
                set.remove((long) nums[i - indexDiff]);
            }
        }
        return false;
    }


}
